package mosdi.util.iterators;

import java.util.Arrays;
import java.util.NoSuchElementException;

import mosdi.fa.CDFA;

/** Iterator that enumerates all patterns of a given length that are
 *  recognized by a given DFA in lexicographical order. */
public class DFALanguageIterator extends LexicographicalIterator {
	private CDFA dfa;
	private int alphabetSize;
	private int length;
	private int leftmostChangedPosition;
	private int nextLeftmostChangedPosition;
	private LexicographicalIterator iterator;
	private int[] next;
	// for each dfa state, the distance to an acception state 
	private int[] distances;
	// for each prefix length, the corresponding dfa state
	private int[] states;
	
	public DFALanguageIterator(CDFA dfa, int length, int alphabetSize) {
		this.dfa = dfa;
		this.length = length;
		this.alphabetSize = alphabetSize;
		iterator = new StringIterator(alphabetSize, length);
		states = new int[length+1];
		Arrays.fill(states, -1);
		states[0] = dfa.getStartState();
		distances = computeDistances();
		leftmostChangedPosition = -1;
		next = getNext();
	}
	
	private int[] computeDistances() {
		int[] result = new int[dfa.getStateCount()];
		for (int state=0; state<result.length; ++state) {
			result[state] = (dfa.getStateOutput(state)>0)?0:Integer.MAX_VALUE;
		}
		for (int i=0; i<length; ++i) { 
			for (int state=0; state<result.length; ++state) {
				for (int c=0; c<alphabetSize; ++c) {
					int target = dfa.getTransitionTarget(state, c);
					if (result[target]<Integer.MAX_VALUE) {
						result[state] = Math.min(result[state], result[target]+1);
					}
				}
			}
		}
		return result;
	}
	
	private int[] getNext() {
		nextLeftmostChangedPosition = length-1;
		while (iterator.hasNext()) {
			int[] s = iterator.next();
			int i=iterator.getLeftmostChangedPosition();
			nextLeftmostChangedPosition = Math.min(nextLeftmostChangedPosition, i);
			for (; i<length; ++i){
				states[i+1] = dfa.getTransitionTarget(states[i], s[i]);
				if (distances[states[i+1]]>=length-i) {
					iterator.skip(i);
					break;
				}
			}
			if (i==length) return s;
		}
		nextLeftmostChangedPosition = -1;
		return null;
	}
	
	@Override
	public boolean hasNext() {
		return next!=null;
	}
	@Override
	public int[] next() {
		if (next==null) throw new NoSuchElementException();
		int[] result = next;
		leftmostChangedPosition = nextLeftmostChangedPosition;
		next = getNext();
		return result;
	}
	@Override
	public void remove() {
		throw new UnsupportedOperationException();
	}

	@Override
	public int getLeftmostChangedPosition() {
		return leftmostChangedPosition;
	}

	@Override
	public int getStringLength() {
		return length;
	}

	@Override
	public int[] peek() {
		if (next==null) throw new NoSuchElementException();
		return next;
	}

	@Override
	public void skip(int position) {
		if (next==null) return;
		if (nextLeftmostChangedPosition<=position) return;
		iterator.skip(position);
		next = getNext();
	}
	
}
